/**
 * 
 */
package algorithm.passed;

import java.util.HashSet;
import java.util.LinkedList;
import java.util.Queue;

/**
 * @author xyyi
 *
 */
public class WordLadder {

	/**
	Given two words (start and end), and a dictionary, find the length of shortest transformation sequence from start to end, such that:

	Only one letter can be changed at a time
	Each intermediate word must exist in the dictionary

	For example,

	Given:
	start = "hit"
	end = "cog"
	dict = ["hot","dot","dog","lot","log"]

	As one shortest transformation is "hit" -> "hot" -> "dot" -> "dog" -> "cog",
	return its length 5.

	Note:

	Return 0 if there is no such transformation sequence.
	All words have the same length.
	All words contain only lowercase alphabetic characters.
	 */
	// BFS
	public int ladderLength(String start, String end, HashSet<String> dict) {

		HashSet<String> visited = new HashSet<String>();
		Queue<String> queue = new LinkedList<String>();
		queue.offer(start);
		visited.add(start);

		int distance = 2;
		while (!queue.isEmpty()) {

			// each time process all words with same distance with start
			int length = queue.size();
			for (int i = 0; i < length; i++) {
				String word = queue.poll();
				StringBuffer sb = new StringBuffer(word);
				for (int j = 0; j < start.length(); j++) {
					char curr = sb.charAt(j);
					for (char ch = 'a'; ch <= 'z'; ch++) {
						if (ch != curr) {
							sb.setCharAt(j, ch);
							String newWord = sb.toString();
							if (!visited.contains(newWord)
							        && dict.contains(newWord)) {
								if (end.equals(newWord)) {
									return distance;
								}
								queue.offer(newWord);
								visited.add(newWord);
							}
						}
					}
					sb.setCharAt(j, curr);
				}
			}
			distance++;
		}

		return 0;
	}

	/**
	 * 
	 */
	public WordLadder() {
		// TODO Auto-generated constructor stub
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub

	}

}
